Corelab Seminar
2018-2019
Vasileios Nakos
Deterministic Modular Subset Sum and Sparse Polynomial Multiplication
Abstract.
We will present the next two results.
1 . In the Modular Subset Sum problem, which is a generalization of the classical Subset Sum problem, one is given n positive integers and is asked if there exists a subset that adds up to a given target t modulo a given integer m. The state of the art is the deterministic algorithm by Koilaris and Xu (SODA 17) which runs in time O (m5/4), and the randomized algorithm of Axiotis, Backurs, Jin, Tzamos and Wu (SODA 19), which runs in O (m) time.
In this work we make considerable progress towards bridging the gap between the deterministic and the randomized case: we devise a deterministic algorithm which runs in O(m1+o(1)) time. In the heart of our approach is lies a careful usage of Kneser’s theorem from Additive Combinatorics, along with a deterministic algorithm for computing the sumset of two sets in output-sensitive time. Using a nearly optimal randomized algorithm for sumset computation our approach reconstructs the result of Axiotis et.al with a Las Vegas algorithm. Furthmore, any subsequent progress to the deterministic version of the aforementioned problem immediately translates to an improved determistic algorithm for Modular Subset Sum.
Joint work with Karl Bringmann
2. We will give a nearly optimal algorithm for multiplying two sparse polynomials in output-sensitive time.
A plethora of open problems will also be discussed.